Digital cameras continue to steadily increase in popularity with consumers. One reason is that the cost of digital cameras continues to decline, making them well within the reach of the average consumer, and causing more consumers to forego traditional film photography in favor of digital cameras. In order to contain cost, many consumer-grade digital color cameras are single-sensor digital cameras. As the name implies, in a single-sensor digital camera only a single image sensor is used to capture color information for each pixel in a color image. Each image sensor, which is typically a charge-coupled device (CCD) or a complementary metal oxide semiconductor (CMOS), is part of a sensor array that together represent the pixels of a color image.
Each image sensor can only generate information about a single color at a given pixel. A color image, however, is represented by combining three separate monochromatic images. In order to display a color image, all of the red, blue and green (RGB) color values are needed at each pixel. In an ideal (and expensive) camera system, each pixel in the sensor array would be provided with three image sensors, each one measuring a red, green or blue pixel color. In a single-sensor digital camera, however, only a single red, blue or green color value can be determined at a given pixel. In order to obtain the other two missing colors, a technique must be used to estimate or interpolate the missing colors from surrounding pixels in the image. This class of estimation and interpolation techniques is called “demosaicing”.
The “demosaicing” term is derived from the fact that a color filter array (CFA) is used in front of the image sensors, with the CFA being arranged in a mosaic pattern. This mosaic pattern has only one color value for each of the pixels in the image. In order to obtain the full-color image, the mosaic pattern must be “demosaiced”. Thus, demosaicing is the technique of interpolating back the image captured with a mosaic-pattern CFA, so that a full RGB value can be associated with every pixel.
More specifically, a single-sensor digital camera captures the image using an image sensor array that is preceded in the optical path by a CFA. A highly common mosaic CFA is called the Bayer mosaic pattern. The Bayer mosaic pattern (or Bayer filter) is shown in FIG. 1. For each 2×2 set of pixels, two diagonally opposed pixels have green filters, and the other two pixels have red and blue filters. Since the color green (G) carries most of the luminance information for humans, its sampling rate is twice that of the color red (R) and the color blue (B). The Bayer filter is described in U.S. Pat. No. 3,971,065 by Bayer entitled “Color Imaging Array”.
There are multitudes of demosaicing techniques available. One of the simplest approaches to demosaicing is bilinear interpolation. In general, bilinear interpolation uses three color planes that are independently interpolated using symmetric bilinear interpolation. This interpolation uses a pixel's nearest neighbors having the same color as the color that is being interpolated. In particular, referring again to FIG. 1, in bilinear interpolation the green value g(i,j) at a pixel position (i,j) that falls in a red or blue pixel is computed by the average of the neighboring green values in a cross pattern, as follows,
                                                                                          g                  ^                                ⁡                                  (                                      i                    ,                    j                                    )                                            =                                                1                  4                                ⁢                                  ∑                                      g                    ⁡                                          (                                                                        i                          +                          m                                                ,                                                  j                          +                          n                                                                    )                                                                                                                                                              (                                  m                  ,                  n                                )                            =                              {                                                      (                                          0                      ,                                              -                        1                                                              )                                    ,                                      (                                          0                      ,                      1                                        )                                    ,                                      (                                                                  -                        1                                            ,                      0                                        )                                    ,                                      (                                          1                      ,                      0                                        )                                                  }                                                                        (        1        )            Equation (1) corresponds to estimating the green value at the pixel marked ‘+’ (also called the “current pixel”) in FIG. 1 as the average of the observed green values marked ‘−’. It should be noted that the current pixel has a red color, and therefore the green and blue color values need to be interpolated. At image boundaries, only pixels that fall within the image are included, and the scaling adjusted.
A graphic illustration of how missing colors are interpolated at a given pixel using bilinear interpolation is shown in FIGS. 2A-H. As shown in FIGS. 2A-H, it should be noted that bilinear techniques typically uses small region of support. The region of support is the size of a pixel neighborhood whose values are considered for the interpolation of any given pixel. As shown in FIGS. 2A-H, the region of support for the bilinear interpolation techniques described below typically is a 3×3 pixel region of support. Using this small of a region of support keeps memory usage and computational complexity to a minimum.
Referring to FIGS. 2A and 2B, illustrated is the bilinear interpolation technique of equation (1) for finding a green color value at a given pixel. In FIG. 2A, a green color value at a red pixel is found by using the green pixels neighboring the red pixel. These neighboring green pixels are marked with a “1” in FIG. 2A. Similarly, in FIG. 2B, a green color value at a blue pixel is found by using the green pixels neighboring the blue pixel. Once again, the green pixels are marked with a “1”.
To find missing red (R) or blue (B) colors, equation (1) still applies. However, now a diagonal cross pattern is used. An exception is that for pixel positions (i,j) that fall in a green pixel only two red neighboring pixels are averaged to produce an interpolated red color value, because there are only two immediately neighboring red pixels. The same is also true for finding blue color values. It should be noted that, besides the computational simplicity of equation (1), its output value is guaranteed to have the same dynamic range of the input value, so no overflow detection and control logic is needed on the output value.
More specifically, FIGS. 2C-E illustrate the bilinear interpolation technique of equation (1) for finding a red color value at a given pixel. Specifically, in FIG. 2C, a red color value is found at a green pixel in a red row and a blue column by using the two red neighboring pixels. Similarly, In FIG. 2D, a red color value at a green pixel in a blue row and a red column is found by using the two neighboring red pixels in the red column. In FIG. 2E, a red color value at a blue pixel is found using the four neighboring red pixels. In FIGS. 2C-E, each of the neighboring red pixels used in the bilinear interpolation technique are marked with a “1”.
Similarly, FIGS. 2F-H illustrate the bilinear interpolation technique of equation (1) for finding a blue color value at a given pixel. Specifically, in FIG. 2F, a blue color value is found at a green pixel in a blue row and a red column by using the two blue neighboring pixels. In FIG. 2G, a blue color value at a green pixel in a red row and a blue column is found by using the two neighboring red pixels in the blue column. In FIG. 2H, a blue color value at a red pixel is found using the four neighboring blue pixels. In FIGS. 2F-H, each of the neighboring blue pixels used in the bilinear interpolation technique are marked with a “1”.
One problem, however, with the above-described bilinear interpolation techniques is that they generate significant artifacts in the color image. This is especially true across edges and other high-frequency content in the image, since bilinear interpolation does not consider the statistical correlation among RGB values. For example, referring to FIGS. 2D and 2F, suppose there is a sharp change in pixel intensity values, so that all pixels in the rightmost column are much brighter than the others. Then, the interpolated blue value of the center pixel (from FIG. 2F) will be somewhat bright, because its blue neighbor to the right is very bright. However, the interpolated red value for that same pixel (from FIG. 2D) will not be bright, because its two red neighbors are not very bright. Therefore, in this case there will be a bright interpolated blue pixel and a not so bright interpolated red pixel; the excess blue and lack of red will make the interpolated pixel color be tinted towards cyan, causing a color fringe artifact. Thus, while bilinear interpolation techniques are fast, computationally non-intensive, and easy to implement, they are also notorious for producing low-quality images due to the significant artifacts (mainly blurriness and color fringing) that they generate.
Better, albeit more complex, interpolation techniques take correlation among RGB values into account. One group of interpolation techniques consider such correlation by using improved linear filters. For example, such a technique is described in a paper by S.-C. Pei and I.-K. Tam entitled “Effective color interpolation in CCD color filter array using signal correlation,” in Proc. ICIP, pp. 488-491, September 2000. Another group of interpolation techniques consider such correlation by using nonlinear filters. These nonlinear filters essentially adapt interpolation smoothness to a measure of image activity or edginess. For example, these nonlinear interpolation techniques are discussed in the following papers: (1) P. Longère, X. Zhang, P. B. Delahunt, and D. H. Brainard, “Perceptual assessment of demosaicing algorithm performance,” Proc. IEEE, vol. 90, pp. 123-132, January 2002; and (2) R. Ramanath, W. E. Snyder, and G. L. Bilbro, “Demosaicking methods for Bayer color arrays,” J. Electronic Imaging, vol. 11, pp. 306-315, July 2002.
Exploiting correlation among RGB channels is the main idea behind improving demosaicing performance in nonlinear interpolation techniques. Specifically, it can be assumed that in a luminance/chrominance decomposition, the chrominance components do not vary much across pixels. In a constant-hue approach described in U.S. Pat. No. 4,724,395 to Freeman entitled, “Median filter for reconstructing missing color samples”, the green channel is bilinearly interpolated and then the red and blue channels are interpolated so as to maintain a constant hue, defined as the R/G and B/G ratios. However, one problem with this technique by Freeman is that even at the expense of computing these ratios, the technique still produces visible artifacts. Moreover, using complex operations (such as division and multiplication) in the computing of interpolations greatly increases the computational complexity, processing overhead, and implementation cost.
Improved results for nonlinear interpolation techniques can be obtained by starting with bilinearly interpolated green pixels and then applying median filters to the interpolated values of the color differences R-G and B-G. Improved performance can be obtained by using gradient-based nonlinear techniques, which typically estimate edge directions and adjust the interpolation formulas so that filtering is performed preferentially along edge directions, and not across them. For example, one gradient-based nonlinear technique is described in U.S. Pat. No. 5,373,322 to C. A. Laroche and M. A. Prescott entitled “Apparatus and method for adaptively interpolating a full color image utilizing chrominance gradients”. The Laroche and Prescott technique interpolates the green channel by using both the red and blue channels to determine edge directions, which determine unequal weights to the terms in equation (1) for the green channel. The color differences R-G and B-G then are interpolated. A technique described in U.S. Pat. No. 5,506,619 to J. E. Adams and J. F. Hamilton, Jr., entitled “Adaptive color plane interpolation in a single color electronic cameras” improves on the Laroche and Prescott technique by considering both first and second order pixel differences (see also J. E. Adams, “Design of practical color filter array interpolation algorithms for digital cameras,” Proc. SPIE, vol. 3028, pp. 117-125, Feb. 1997). These gradient techniques, however, merely compute a gradient and use it to select which interpolation technique to use.
A technique described in a paper by E. Chang, S. Cheung, and D. Y. Pan, entitled “Color filter array recovery using a threshold-based variable number of gradients,” in Proc. SPIE, vol. 3650, pp. 36-43, Jan. 1999, is an improvement on the above techniques by considering a variable number of gradients. A simpler but efficient algorithm that uses soft decision rules to combine interpolation results from horizontal and vertical directions is presented in a paper by X. Wu and N. Zhang, entitled “Primary-consistent soft-decision color demosaic for digital cameras,” in Proc. ICIP, vol. 1, pp. 477-480, September 2003.
Iterative methods can lead to further improvement by using results from blue and red interpolations to correct the green interpolation, and vice-versa. That is the basis of a technique described in a paper by R. Kimmel, “Demosaicing: image reconstruction from color CCD samples,” IEEE Trans. on Image Processing, vol. 8, pp. 1221-1228, September 1999. In Kimmel's approach, the interpolation steps are based on a combination of the constant-hue and gradient-based methods. A technique based on iterative projections is presented in a paper by B. K. Gunturk, Y. Altunbasak, and R. M. Mersereau, entitled “Color plane interpolation using alternating projections”, in IEEE Trans. on Image Processing, vol. 11, pp. 997-1013, September 2002. The Gunturk technique has the best performance to date on a popular set of standard test images. One problem, however with the Gunturk technique is that it has a very high complexity (as many as 480 operations per input pixel).
The above-described nonlinear interpolation techniques typically use a larger region of support that is used in bilinear interpolation techniques. For example, a 5×5 pixel region of support is typical for these nonlinear techniques. A 5×5 region of support yields good correlation between RGB values and produce high-quality images. A smaller region of support greatly reduces the image quality, while larger regions of support require more memory and greatly increase computational complexity.
Therefore, what is needed is an interpolation technique for demosaicing color images that retains the simplicity and speed of the bilinear interpolation technique while producing the high-quality images of more complex techniques, such as nonlinear interpolation techniques. What is also needed is a high-quality interpolation technique that considers correlation among RGB values to improve performance. What is further needed is an interpolation technique that considers this correlation by computing a gradient and uses this computed gradient directly as a correction term and not merely to select an interpolation technique. What is also needed is an interpolation technique that utilizes a larger region of support than bilinear techniques (where the region of support is comparable to that used in nonlinear techniques) for improved quality. What is further needed is an interpolation technique that requires only simple mathematical operations (such as addition) when computing interpolations to increase speed, avoid computational complexity, and allow inexpensive implementation.